
//comp为传进来的优先级
function PriorityList(comp, data) {
    this.arr = data || [];
    this.length = this.arr.length;
    this.comp = comp || function (a, b) { return a - b };
}
//放进去，自动根据优先级排列
PriorityList.prototype.push = function (x) {
    this.arr.push(x);
    this.length++;
    _up(this.arr,this.length-1,this.comp);
    // heapSet(this.arr, this.comp);
}

//将优先级最高的取出来，取出来后优先级最高的放在最前面
PriorityList.prototype.pop = function () {
    if (this.length === 0) return undefined;
    let temp = this.arr.shift();
    this.length--;
    [this.arr[0], this.arr[this.length - 1]] = [this.arr[this.length - 1], this.arr[0]];
    _down(this.arr,0,this.length,this.comp)
    // heapSet(this.arr, this.comp);
    return temp;
}
//将最优先的展示出来
PriorityList.prototype.top = function () {
    if (this.length === 0) return undefined;
    return this.arr[0];
}
//初始化这个优先队列
PriorityList.prototype.init = function () {
    // console.log(this.arr);
    // console.log(this.comp);
    heapSet(this.arr, this.comp);
}

//调整堆
function heapAdjust(arr, index, len, comp) {
    while (2 * index + 1 < len) {
        let cur = 2 * index + 1;
        if (cur + 1 < len) cur = comp(arr[cur + 1], arr[cur]) >= 0 ? cur + 1 : cur;
        if (comp(arr[index], arr[cur]) < 0) {
            [arr[index], arr[cur]] = [arr[cur], arr[index]];
            index = cur;
        } else break;
    }
}
//上浮，每次将一个新元素加入到数组的最后一位时，进行上浮
function _up(arr, index, comp) {
    while (index !== 0) {
        let tempIndex = Math.floor((index - 1) / 2);
        if (comp(arr[tempIndex], arr[index]) < 0) {
            [arr[index], arr[tempIndex]] = [arr[tempIndex], arr[index]];
            index = tempIndex;
        } else break;
    }
}

function _down(arr, index, len, comp) {
    heapAdjust(arr, index, len, comp);
}

//初始化堆
function heapSet(arr, comp) {
    let len = arr.length;
    console.log(arr);
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        heapAdjust(arr, i, len, comp)
    }
}


let plist = new PriorityList((a, b) => a - b, [3, 4, 2, 1, 6, 7]);
plist.init();
plist.pop();
plist.push(34);
plist.push(34);
plist.pop();
plist.pop();
console.log(plist.top());
